package com.pan.alg.niuke.stackque;

import java.util.ArrayList;
import java.util.PriorityQueue;

/**
 * 给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。
 * 数据范围：0\le k,n \le 100000≤k,n≤10000，数组中每个数的大小0 \le val \le 10000≤val≤1000 要求：空间复杂度 O(n)O(n) ，时间复杂度
 * O(nlogk)O(nlogk)
 */
public class GetLeastKNumbers {

    public ArrayList<Integer> GetLeastNumbersSolution(int [] input, int k) {

        ArrayList<Integer> res = new ArrayList<>();
        //排除特殊情况
        if(k == 0 || input.length == 0){
            return res;
        }
            
        //大根堆
        PriorityQueue<Integer> bq = new PriorityQueue<>((o1, o2)->o2.compareTo(o1));
        
        for(int i=0;i<k;i++){
            bq.offer(input[i]);
        }
        
        for(int i=k;i<input.length;i++){
            int i1 = input[i];
            if(bq.peek().compareTo(i1)>0){
                bq.poll();
                bq.offer(i1);
            }
        }

        for (int i = 0; i < k; i++) {
            //
            res.add(bq.poll());
        }

        return res;
    }
}
